package com.example.zxd;

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

/**
 * 单源最短路<p>
 * 描述：
 * 给一个n(1≤n≤2500)
 * 个点m(1≤m≤6200)
 * 条边的无向图，求s
 * 到t
 * 的最短路。
 *<p>
 * 输入：
 * 第一行四个由空格隔开的整数n
 * 、m
 * 、s
 * 、t
 * 。
 *<p>
 * 之后的m
 * 行，每行三个正整数si
 * 、ti
 * 、wi(1 ≤ wi ≤ 10^9)
 * ，表示一条从si
 * 到ti
 * 长度为wi
 * 的边。
 *<p>
 * 输出：
 * 一个整数表示从s
 * 到t
 * 的最短路长度。数据保证至少存在一条道路。
 *<p>
 * 样例输入：<p>
 * 7 11 5 4<p>
 * 2 4 2<p>
 * 1 4 3<p>
 * 7 2 2<p>
 * 3 4 3<p>
 * 5 7 5<p>
 * 7 3 3<p>
 * 6 1 1<p>
 * 6 3 4<p>
 * 2 4 3<p>
 * 5 6 3<p>
 * 7 2 1<p>
 * 样例输出：<p>
 * 7
 * @author: scarborough
 * @datetime: 2025/3/19 - 16:16
 * @status: compiling
 */
public class PROB1009 {
    static class Edge {
        int to;
        long weight;

        Edge(int to, long weight) {
            this.to = to;
            this.weight = weight;
        }
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int m = sc.nextInt();
        int n = sc.nextInt();
        int s = sc.nextInt();
        int t = sc.nextInt();

        // 构建邻接表，节点编号从 1 到 n
        List<Edge>[] graph = new ArrayList[n + 1];
        for (int i = 1; i <= n; i++) {
            graph[i] = new ArrayList<>();
        }

        // 读取 m 条边的输入，无向图需要添加两个方向的边
        for (int i = 0; i < m; i++) {
            int u = sc.nextInt();
            int v = sc.nextInt();
            long w = sc.nextLong();
            graph[u].add(new Edge(v, w));
            graph[v].add(new Edge(u, w));
        }
        sc.close();


    }
}
